package com.klun.project.common.constans.leetcode;
//设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
// 如果指定节点没有对应的“下一个”节点，则返回null。
// 示例 1:
// 输入: root = [2,1,3], p = 1
//  2
// / \
//1   3
//输出: 2
//
// 示例 2:
// 输入: root = [5,3,6,2,4,null,null,1], p = 6
//      5
//     / \
//    3   6
//   / \
//  2   4
// /
//1
//输出: null
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树
// 👍 211 👎 0

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

public class Solution0406 {

	public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
		if (root == null) return null;
		if (root.val <= p.val) return inorderSuccessor(root.right, p);
		TreeNode ans = inorderSuccessor(root.left, p);
		return ans == null ? root : ans;
	}

	public static void main(String[] args) {
		Solution0406 solution = new Solution0406();
//		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
//		TreeNode insert = ParseUtils.ArrayToBTree("[2,1,3]");
		TreeNode insert = ParseUtils.ArrayToBTree("[5,3,6,2,4,null,null,1]");
		TreeNode treeNode = solution.inorderSuccessor(insert, new TreeNode(6));
		System.out.println(treeNode.val);
	}
}
